package leetcode.bytedance;


import java.io.*;

/**
 * 某公司游戏平台的夏季特惠开始了，你决定入手一些游戏。现在你一共有X元的预算，该平台上所有的 n 个游戏均有折扣，标号为 i 的游戏的原价 a
 * i
 * ​
 * 元，现价只要 b
 * i
 * ​
 * 元（也就是说该游戏可以优惠 a
 * i
 * ​
 * −b
 * i
 * ​
 * 元）并且你购买该游戏能获得快乐值为 w
 * i
 * ​
 * 。由于优惠的存在，你可能做出一些冲动消费导致最终买游戏的总费用超过预算，但只要满足获得的总优惠金额不低于超过预算的总金额，那在心理上就不会觉得吃亏。现在你希望在心理上不觉得吃亏的前提下，获得尽可能多的快乐值。
 * <p>
 * 格式：
 * <p>
 * 输入：
 * - 第一行包含两个数 n 和 X 。
 * - 接下来 n 行包含每个游戏的信息，原价 ai,现价 bi，能获得的快乐值为 wi 。
 * 输出：
 * - 输出一个数字，表示你能获得的最大快乐值。
 * 示例 1：
 * <p>
 * 输入：
 * 4 100
 * 100 73 60
 * 100 89 35
 * 30 21 30
 * 10 8 10
 * 输出：100
 * 解释：买 1、3、4 三款游戏，获得总优惠 38 元，总金额 102 元超预算 2 元，满足条件，获得 100 快乐值。
 * 示例 2：
 * <p>
 * 输入：
 * 3 100
 * 100 100 60
 * 80 80 35
 * 21 21 30
 * 输出：60
 * 解释：只能买下第一个游戏，获得 60 的快乐值。
 * 示例 3：
 * <p>
 * 输入：
 * 2 100
 * 100 30 35
 * 140 140 100
 * 输出：135
 * 解释：两款游戏都买，第一款游戏获得优惠 70 元，总开销 170 元，超过预算 70 元，超出预算金额不大于获得优惠金额满足条件，因此可以获得最大快乐值为 135。
 * 提示：
 * <p>
 * 所有输入均为整型数
 * 1 <= n <= 500
 * 0 <= x <= 10,000
 * 0 <= b_i <= a_i <= 500
 * 1 <= w_i <= 1,000,000,000
 * 关于数据集：
 * 前 30% 的数据， 小数据集 (n<=15)
 * 中间 30% 的数据，中等数据集 (n<=100)
 * 后 40% 的数据，大数据集 (n<=500)
 */
public class Bytedance006 {

    static int n;
    static int x;
    static int m;

    static int[] costi = new int[501];
    static int[] vali = new int[501];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

        while (in.nextToken() != StreamTokenizer.TT_EOF) {
            n = (int) in.nval;
            in.nextToken();
            x = (int) in.nval;
            m = 1;
            int ai, bi, hi, ti, ans, ans1 = 0;
            for (int i = 1; i <= n; i++) {
                in.nextToken();
                ai = (int) in.nval;
                in.nextToken();
                bi = (int) in.nval;
                in.nextToken();
                hi = (int) in.nval;

                ti = bi - (ai - bi);

//                System.out.printf("==%d %d %d==", ai, bi, hi);
                if (ti <= 0) {
                    ans1 += hi;
                    x -= ti;
                } else {
                    costi[m] = ti;
                    vali[m] = hi;
                    m++;
                }
            }
            ans = ans1 + f(x, m, costi, vali);
            out.println(ans);
        }
        out.flush();
        out.close();
        br.close();
    }

    static int f(int t, int m, int[] costi, int[] vali) {
        int[][] dp = new int[m + 1][t + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= t; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= costi[i]) {
                    dp[i][j] = Math.max(dp[i][j], vali[i] + dp[i - 1][j - costi[i]]);
                }
            }
        }
        return dp[m][t];
    }
}
